﻿/*
 * @autor: hectorea
 * @date: 02/08/12
 * @project: SquareRoot
 * @Reference:
 *  http://en.wikipedia.org/wiki/Binary_tree
 *  http://en.wikipedia.org/wiki/Depth-first_search
 *  http://en.wikipedia.org/wiki/Breadth-first_search
 *  http://classes.soe.ucsc.edu/cmps012b/Spring97/Lecture16/sld008.htm
 *  http://tekpool.wordpress.com/2006/11/04/binary-tree-traversal-breadth-first-aka-width-first-aka-level-order/
 */

using System;

namespace BinaryTrees
{
    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree btree = LoadBTree3();
            //Console.WriteLine("Is Balanced? {0}", btree.IsBalanced(btree.Root));
            Console.WriteLine("Is BST? {0}", btree.IsBinarySearchTree(btree.Root));

            //Console.WriteLine("InOrder Traversal");
            //btree.InOrder(btree.Root);
            //Console.ReadLine();

            //Console.WriteLine("PreOrder Traversal");
            //btree.PreOrder(btree.Root);
            //Console.ReadLine();

            //Console.WriteLine("PostOrder Traversal");
            //btree.PostOrder(btree.Root);
            //Console.ReadLine();

            //Console.WriteLine("BreadthFirst Traversal");
            //btree.BreadthFirst(btree.Root);
            //Console.ReadLine();

            //Console.WriteLine("LowestCommonAncestor");
            //BinaryTreeNode p = btree.Root.Left.Right;
            //BinaryTreeNode q = btree.Root.Left.Left.Right;
            //BinaryTreeNode lca = btree.LowestCommonAncestor(btree.Root, p, q);
            //Console.WriteLine("The LCA between {0} and {1} is {2}", p.Value, q.Value, lca.Value);
            
            Console.ReadLine();                                            
        }

        /// <summary>
        ///                                                            1
        ///                                                          /   \
        ///                                                        2       3
        ///                                                      /  \     /  \
        ///                                                     4    5    6   7
        ///                                                      \
        ///                                                       8
        /// 
        /// </summary>
        /// <returns>A BinaryTree </returns>
        private static BinaryTree LoadBTree1()
        {
            BinaryTree btree = new BinaryTree();
            btree.Root = new BinaryTreeNode(1);
            btree.Root.Left = new BinaryTreeNode(2);
            btree.Root.Right = new BinaryTreeNode(3);

            btree.Root.Left.Left = new BinaryTreeNode(4);
            btree.Root.Left.Right = new BinaryTreeNode(5);

            btree.Root.Right.Left = new BinaryTreeNode(6);
            btree.Root.Right.Right = new BinaryTreeNode(7);

            btree.Root.Left.Left.Right = new BinaryTreeNode(8);
            //btree.Root.Left.Left.Right.Right = new BinaryTreeNode(10);

            return btree;
        }

        /// <summary>
        ///                                                            3
        ///                                                          /   \
        ///                                                        5       1
        ///                                                      /  \     /  \
        ///                                                     6    2    0   8
        ///                                                         / \
        ///                                                        7   4
        /// 
        /// </summary>
        /// <returns>A BinaryTree </returns>
        private static BinaryTree LoadBTree2()
        {
            BinaryTree btree = new BinaryTree();
            btree.Root = new BinaryTreeNode(3);
            btree.Root.Left = new BinaryTreeNode(5);
            btree.Root.Right = new BinaryTreeNode(1);

            btree.Root.Left.Left = new BinaryTreeNode(6);
            btree.Root.Left.Right = new BinaryTreeNode(2);

            btree.Root.Right.Left = new BinaryTreeNode(0);
            btree.Root.Right.Right = new BinaryTreeNode(8);

            btree.Root.Left.Right.Left = new BinaryTreeNode(7);
            btree.Root.Left.Right.Right = new BinaryTreeNode(4);

            return btree;
        }


        private static BinaryTree LoadBTree3()
        {
            BinaryTree btree = new BinaryTree();
            btree.Root = new BinaryTreeNode(23);
            btree.Root.Left = new BinaryTreeNode(16);
            btree.Root.Right = new BinaryTreeNode(45);

            btree.Root.Left.Left = new BinaryTreeNode(3);
            btree.Root.Left.Right = new BinaryTreeNode(22);

            btree.Root.Right.Left = new BinaryTreeNode(37);
            btree.Root.Right.Right = new BinaryTreeNode(99);

            
            return btree;
        }
    }
}
